In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the Pappus graph is a
bipartite 3-
regular undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
with 18 vertices and 27 edges, formed as the
Levi graph
In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure.. See in particulap. 181 From a collection of points and lines in an incidence geometry or a projective configuration, we form ...
of the
Pappus configuration
In geometry, the Pappus configuration is a configuration of nine points and nine lines in the Euclidean plane, with three points per line and three lines through each point.
History and construction
This configuration is named after Pappus of ...
. It is named after
Pappus of Alexandria
Pappus of Alexandria (; grc-gre, Πάππος ὁ Ἀλεξανδρεύς; AD) was one of the last great Greek mathematicians of antiquity known for his ''Synagoge'' (Συναγωγή) or ''Collection'' (), and for Pappus's hexagon theorem i ...
, an ancient
Greek mathematician who is believed to have discovered the "hexagon theorem" describing the Pappus configuration. All the
cubic distance-regular graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and .
...
s are known; the Pappus graph is one of the 13 such graphs.
The Pappus graph has
rectilinear crossing number 5, and is the smallest cubic graph with that crossing number . It has
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
6, diameter 4, radius 4,
chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
2,
chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
3 and is both 3-
vertex-connected and 3-
edge-connected. It has
book thickness
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie o ...
3 and
queue number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
Defin ...
2.
The Pappus graph has a
chromatic polynomial
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study ...
equal to:
.
The name "Pappus graph" has also been used to refer to a related nine-vertex graph, with a vertex for each point of the Pappus configuration and an edge for every pair of points on the same line; this nine-vertex graph is 6-regular, is the
complement graph
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a ...
of the union of three disjoint
triangle graph
In the mathematical field of graph theory, the triangle graph is a planar undirected graph with 3 vertices and 3 edges, in the form of a triangle.
The triangle graph is also known as the cycle graph C_3 and the complete graph K_3.
Properties ...
s, and is the complete tripartite graph K
3,3,3. The first Pappus graph can be embedded in the torus to form a self-
Petrie dual
In topological graph theory, the Petrie dual of an embedded graph (on a 2-manifold with all faces disks) is another embedded graph that has the Petrie polygons of the first embedding as its faces.
The Petrie dual is also called the Petrial, and t ...
regular map with nine hexagonal faces; the second, to form a regular map with 18 triangular faces. The two regular toroidal maps are dual to each other.
Algebraic properties
The automorphism group of the Pappus graph is a group of order 216. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore the Pappus graph is a
symmetric graph
In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism
:f : V(G) \rightarrow V(G)
such that
:f(u_1) = u_2 and f(v_1) = v_2.
In oth ...
. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the ''Foster census'', the Pappus graph, referenced as F018A, is the only cubic symmetric graph on 18 vertices.
[ Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.]
The
characteristic polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The chara ...
of the Pappus graph is
. It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
Gallery
Image:Pappus graph colored.svg, Pappus graph coloured to highlight various cycles.
Image:Pappus graph 3color edge.svg, The chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
of the Pappus graph is 3.
Image:Pappus graph 2COL.svg, The chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
of the Pappus graph is 2.
Image:Pappus graph as regular map.png, The Pappus graph embedded in the torus, as a regular map with nine hexagonal faces.
Image:Pappus-graph-on-torus.png, The Pappus graph and associated map embedded in the torus.
References
{{reflist
Individual graphs
Regular graphs